package com.zklh.leetcode.interviewTop150;

import java.util.ArrayList;
import java.util.List;

/**
 * 被围绕的区域
 * author: tongnan
 * date: 2024/8/1
 */
public class Solution139 {
    public void solve(char[][] board) {
        List<int[]> trace = new ArrayList<>();

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                trace.clear();
                if (board[x][y] == 'O') {
                    if (!reachBoundary(board, trace, x, y)) {
                        setTraceValue(board, trace, 'X');
                    }
                }
            }
        }

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                trace.clear();
                if (board[x][y] == 'V') {
                    board[x][y] = 'O';
                }
            }
        }

    }

    private boolean reachBoundary(char[][] board, List<int[]> trace, int x, int y) {
        if (x > board.length-1 || y > board[0].length-1 || x < 0 || y < 0) {
            return true;
        }
        if (board[x][y] == 'O') {
            trace.add(new int[]{x, y});
            board[x][y] = 'V';
            return (reachBoundary(board, trace, x+1, y) | reachBoundary(board, trace, x, y + 1) | reachBoundary(board, trace, x, y - 1) | reachBoundary(board, trace, x-1, y));
        }
        return false;
    }

    private void setTraceValue(char[][] board, List<int[]> trace, char value) {
        for (int[] ints : trace) {
            board[ints[0]][ints[1]] = value;
        }
    }

    public static void main(String[] args) {
        Solution139 solution139 = new Solution139();
        char[][] board = {
                {'O','O','O','O','X','X'},
                {'O','O','O','O','O','O'},
                {'O','X','O','X','O','O'},
                {'O','X','O','O','X','O'},
                {'O','X','O','X','O','O'},
                {'O','X','O','O','O','O'}};
        solution139.solve(board);
        System.out.println(111);
    }

}
